{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Coding Practice\n",
    "- 链表\n",
    "- 二叉树\n",
    "- 动态规划\n",
    "- NP问题\n",
    "- 滑动窗口\n",
    "- 回溯算法\n",
    "- 贪心算法\n",
    "- Python内存机制（与C++、Java对比）\n",
    "- Python原生数据结构的操作符效率比较\n",
    "- 其他细节"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 链表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# leetcode中普通链表节点表示方式一般有两种\n",
    "class ListNode:\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "class ListNode:\n",
    "    def __init__(self,val=0,next=None):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "\n",
    "# 其他情况也有，不过核心还是上面两种定义方式\n",
    "class ListNode:\n",
    "    def __init__(self,val,next,random):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "        self.random=random\n",
    "\n",
    "# 可以发现leetcode上面C++链表节点定义大部分是用struct。\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 但是往往Leetcode给我的是一个列表，我们如果想要本地调试代码的话，要自己生成一个链表。\n",
    "# 所以我们需要设计函数，根据所给的列表(list)生成一个链表(ListNode)[不带头节点，在leetcode中第一个节点叫做head，leetcode的定义与我们在数据结构这门课上学的定义不同，注意一下就行，本质一样]\n",
    "# 以第一种方式为例\n",
    "class ListNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "\n",
    "# 写法一:最暴力的写法，时间O(N),空间O(N),而且产生了很多没用的东西，可以return nodes[i]\n",
    "def gen_linklist_from_list_1(arg_list:list)->ListNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    nodes=[ListNode(_) for _ in arg_list]\n",
    "    for index in range(len(nodes)-1):\n",
    "        nodes[index].next=nodes[index+1]\n",
    "    return nodes[0]\n",
    "    \n",
    "# 不要创建一个nodes列表，只要有一个head就行,，时间O(N),空间O(1)\n",
    "def gen_linklist_from_list_2(arg_list:list)->ListNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    head=ListNode(arg_list[0])\n",
    "    cur=head\n",
    "    for _ in arg_list[1::]:\n",
    "        cur.next=ListNode(_)\n",
    "        cur=cur.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 以第二种方式为例\n",
    "class ListNode:\n",
    "    def __init__(self,val=0,next=None):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "\n",
    "##  以下内容和第一种方式一摸一样，一个字母都没改，完全ok\n",
    "##  重复记录有点傻逼，但是该文档是为了分享，方便直接测试\n",
    "\n",
    "\n",
    "# 写法一:最暴力的写法，时间O(N),空间O(N),而且产生了很多没用的东西，可以return nodes[i]\n",
    "def gen_linklist_from_list_1(arg_list:list)->ListNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    nodes=[ListNode(_) for _ in arg_list]\n",
    "    for index in range(len(nodes)-1):\n",
    "        nodes[index].next=nodes[index+1]\n",
    "    return nodes[0]\n",
    "    \n",
    "# 不要创建一个nodes列表，只要有一个head就行,，时间O(N),空间O(1)\n",
    "def gen_linklist_from_list_2(arg_list:list)->ListNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    head=ListNode(arg_list[0])\n",
    "    cur=head\n",
    "    for _ in arg_list[1::]:\n",
    "        cur.next=ListNode(_)\n",
    "        cur=cur.next\n",
    "    return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "## 测试代码\n",
    "li=[1,2]\n",
    "# link=gen_linklist_from_list_1(li)\n",
    "link=gen_linklist_from_list_2(li)\n",
    "print(link.val)\n",
    "print(link.next.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 来看一段代码："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./pics/lly.png)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 该定义为两个参数的定义方式。\n",
    "# 首先这种写法正如他自己所说顺序为9，8，7...是倒的，其实用倒序索引不久完了吗。\n",
    "# 然后那段代码竟然用栈的思想，先放到一个List再pop出来，啊这，以毒攻毒吧\n",
    "# 而且这种写法有瑕疵，因为它和leetcode的链表结构不一样，他后面多了一个val为None的节点，leetcode是没有这个东西的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 优化一下他\n",
    "class ListNode:\n",
    "    def __init__(self,val=0,next=None):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "\n",
    "def gen_linklist_from_list_3(arg_list:list)->ListNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    head=ListNode(arg_list[-1])\n",
    "    for _ in arg_list[-2::-1]:\n",
    "        head=ListNode(_,head)\n",
    "    return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "## 测试代码\n",
    "li=[1,2]\n",
    "link=gen_linklist_from_list_3(li)\n",
    "print(link.val)\n",
    "print(link.next.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 链表具体习题\n",
    "\n",
    "## 简单题：\n",
    "# 剑指 Offer 06. 从尾到头打印链表\n",
    "# 剑指 Offer 22. 链表中倒数第k个节点\n",
    "# 206. 反转链表\n",
    "# 21. 合并两个有序链表\n",
    "# 160. 相交链表\n",
    "\n",
    "\n",
    "## 中等题：\n",
    "# 138. 复制带随机指针的链表\n",
    "\n",
    "\n",
    "## 困难题：\n",
    "# 23. 合并K个升序链表(也可利用小顶堆)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# leetcode中树的节点一般表示为：\n",
    "class TreeNode:\n",
    "    def __init__(self,val=0,left=None,right=None):\n",
    "        self.val=val\n",
    "        self.left=left\n",
    "        self.right=right\n",
    "# 同理，如果我们想本地调试代码，我们要自己生成一棵树。\n",
    "# 参照leetcode上的形式，root = [3,9,20,null,null,15,7]，leetcode上给出的树是一个列表形式。\n",
    "# 这种形式就是完全二叉树的形式，将不存在的节点设置成None就行了。（准确来说，是要比完全二叉树还要严格一点，但是又不如满二叉树严格）\n",
    "\n",
    "# 如果是生成一颗无规则的树，是没有算法的，只有一个一个插入。除非像数学家一样加入限定条件，然后又在限定条件下动手。\n",
    "# 但是这里是有规则的，类似满二叉的形式，如果上过数据结构，学过层序遍历的话，这显然是层序遍历的思想。\n",
    "# 层序遍历，用的就是广度优先算法，利用的数据结构是队列。\n",
    "\n",
    "def gen_binarytree_from_list(arg_list:list)->TreeNode:\n",
    "    if arg_list==[]:\n",
    "        return None\n",
    "    queue=[]\n",
    "    root=TreeNode(arg_list[0])\n",
    "    queue.append(root)\n",
    "    index=1\n",
    "    while index<=len(arg_list)-2:\n",
    "        cur=queue.pop(0)            #每次进入循环都更新了cur，让cur一直是队列中最左边的节点\n",
    "        if arg_list[index] is not None:\n",
    "            leftnode=TreeNode(arg_list[index])\n",
    "            cur.left=leftnode\n",
    "            queue.append(leftnode)\n",
    "        if arg_list[index+1] is not None:\n",
    "            rightnode=TreeNode(arg_list[index+1])\n",
    "            cur.right=rightnode\n",
    "            queue.append(rightnode)\n",
    "        index+=2\n",
    "    return root\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# 测试代码\n",
    "root=[1,2,5,3,4,None,6]\n",
    "root=gen_binarytree_from_list(root)\n",
    "print(root.left.left.val)\n",
    "print(root.right.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 二叉树最基本的就是遍历\n",
    "# 必须理解前中后序遍历和层序遍历，而且能够实现\n",
    "# 因为这也对应着深度优先和广度优先的思想，以及加深对递归和迭代的理解\n",
    "\n",
    "# 前序遍历：\n",
    "def preorder(arg_tree)->list:\n",
    "    r_=[]\n",
    "    # r_.append(tree.val)\n",
    "    # preoreder(tree.left)\n",
    "    # preoreder(tree.right)\n",
    "    def helpfun(tree):\n",
    "        if tree is None:\n",
    "            return\n",
    "        r_.append(tree.val)\n",
    "        helpfun(tree.left)\n",
    "        helpfun(tree.right)\n",
    "    helpfun(arg_tree)\n",
    "    return r_\n",
    "\n",
    "# 假设树的节点是N，叶子节点数是L，时间复杂度O(N),空间复杂度就是O(N+L)，可以认为都是O(N)。\n",
    "\n",
    "\n",
    "# 中序遍历：\n",
    "def midorder(arg_tree)->list:\n",
    "    r_=[]\n",
    "    def helpfun(tree):\n",
    "        if tree is None:\n",
    "            return\n",
    "        helpfun(tree.left)\n",
    "        r_.append(tree.val)\n",
    "        helpfun(tree.right)\n",
    "    helpfun(arg_tree)\n",
    "    return r_\n",
    "\n",
    "# 后序遍历：\n",
    "def postorder(arg_tree)->list:\n",
    "    r_=[]\n",
    "    def helpfun(tree):\n",
    "        if tree is None:\n",
    "            return \n",
    "        helpfun(tree.left)\n",
    "        helpfun(tree.right)\n",
    "        r_.append(tree.val)\n",
    "    helpfun(arg_tree)\n",
    "    return r_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "前序遍历： [1, 2, 3, 4, 5, 6]\n",
      "中序遍历： [3, 2, 4, 1, 5, 6]\n",
      "后序遍历： [3, 4, 2, 6, 5, 1]\n"
     ]
    }
   ],
   "source": [
    "print(f'前序遍历： {preorder(root)}')\n",
    "print(f'中序遍历： {midorder(root)}')\n",
    "print(f'后序遍历： {postorder(root)}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 复习一下C语言课上学的函数调用：\n",
    "\n",
    "# 函数栈如下图所示\n",
    "# 递归就是系统帮我们维护这个函数栈，每次新调用一个函数，栈顶就会把函数地址加进去，该函数结束就出栈\n",
    "# 如果想把递归写成迭代的话，就要自己维护这个函数栈。\n",
    "# 我尝试了，暂时写不出来，诶呀妈的智商差劲\n",
    "# 当然菜狗可以说说为了代码的可读性，我们只写递归，比如菜狗我\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./pics/%E5%87%BD%E6%95%B0%E6%A0%88.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 二叉树具体习题\n",
    "\n",
    "## 简单\n",
    "# 144. 二叉树的前序遍历\n",
    "# 104. 二叉树的最大深度\n",
    "# 110. 平衡二叉树\n",
    "# 100. 相同的树\n",
    "# 101. 对称二叉树\n",
    "# 226. 翻转二叉树\n",
    "\n",
    "## 中等\n",
    "# 102. 二叉树的层序遍历\n",
    "# 107. 二叉树的层序遍历 II\n",
    "# 662. 二叉树最大宽度\n",
    "\n",
    "\n",
    "## 困难\n",
    "# 297. 二叉树的序列化与反序列化\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "### 习题合辑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### DP路径问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## DP路径问题\n",
    "\n",
    "# 62. 不同路径\n",
    "# 63. 不同路径 II\n",
    "# 64. 最小路径和\n",
    "# 120. 三角形最小路径和\n",
    "# 931. 下降路径最小和\n",
    "# 1289. 下降路径最小和 II\n",
    "# 1575. 统计所有可行路径(呜呜呜真难啊，我先放弃一下)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### DP背包问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "## DP背包问题\n",
    "\n",
    "## 暂时只记录01背包和完全背包问题\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 01背包问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 01背包问题\n",
    "\n",
    "# 问题描述：给定价值数组value=[a,b,c,d],重量数组weight=[w,x,y,z],给定背包容量W,在不超过背包容量W的情况，让价值最大化。\n",
    "# 至于为什么叫做01，是因为该物品无法拆分，只能取或者不取。\n",
    "\n",
    "# 测试用例：\n",
    "# w=[10,20,30],value=[60,100,120],W=50,val_max=220\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 穷举法暴力解法，这是最暴力的解法，没有人会无聊至此，网上也没人写这个代码，我想了好一会儿才写出来。主要是灵光一现想到用二进制，不然这个代码写不出了。\n",
    "def search_exh(arg_weight,arg_value,arg_W):\n",
    "    val_max=0\n",
    "    n=len(arg_value)\n",
    "    # index_arr_01=[0]*n\n",
    "    val_arr=[]\n",
    "    # weight_arr=[]\n",
    "    for i in range(0,2**n):\n",
    "        index_arr_01=[int(j) for j in list(format(i,\"b\"))]\n",
    "        ## index_arr_01有可能不和arg_weight等长，把前面缺少的数位补0，debug时候发现的\n",
    "        if len(index_arr_01)<n:\n",
    "            for i in range(0,n-len(index_arr_01)):\n",
    "                index_arr_01.insert(0,0)\n",
    "        index_arr=[index for index,_ in enumerate(index_arr_01) if _ ==1]\n",
    "        weight_total=0\n",
    "        for _ in index_arr:\n",
    "            weight_total+=arg_weight[_]\n",
    "        if weight_total<=arg_W:\n",
    "            val_total=0\n",
    "            for _ in index_arr:\n",
    "                val_total+=arg_value[_]\n",
    "            val_arr.append(val_total)\n",
    "    val_max=max(val_arr)\n",
    "    return val_max\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试通过，时间复杂度2**n，空间复杂度2**n，最暴力，除了我这种无聊的傻逼，应该没人写这东西。准确来说，应该是n*2**n，无所谓了，面试写这个直接挂的。\n",
    "w=[10,20,30]\n",
    "value=[60,100,120]\n",
    "W=50\n",
    "search_exh(w,value,W)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 当然，这个问题还可以用递归解决\n",
    "def recur_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    # 递归终止条件\n",
    "    if arg_W<=0 or n==0:\n",
    "        return 0\n",
    "    # 否则就返回两种情况中的较大值\n",
    "    v_tmp=arg_value[0]\n",
    "    w_tmp=arg_weight[0]\n",
    "    # w_tmp=arg_weight.pop(0)\n",
    "    # v_tmp=arg_value.pop(0)\n",
    "    weight_left=arg_weight[1:]\n",
    "    value_left=arg_value[1:]\n",
    "\n",
    "    # value1=v_tmp+recur_solve(wei_tmp,val_tmp,arg_W-w_tmp)\n",
    "    # if w_tmp>arg_W:\n",
    "    #     value1=recur_solve(weight_left,value_left,arg_W)\n",
    "    # else:\n",
    "    #     value1=v_tmp+recur_solve(weight_left,value_left,arg_W-w_tmp)\n",
    "    # value2=recur_solve(weight_left,value_left,arg_W)\n",
    "    if w_tmp>arg_W:\n",
    "        return recur_solve(weight_left,value_left,arg_W)\n",
    "    else:\n",
    "        return max(v_tmp+recur_solve(weight_left,value_left,arg_W-w_tmp),recur_solve(weight_left,value_left,arg_W))\n",
    "    # return max(value1,value2)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[10,20,30]\n",
    "value=[60,100,120]\n",
    "W=50\n",
    "recur_solve(w,value,W)\n",
    "\n",
    "# 递归其实思路是简单的，但是要注意细节，这个代码我一开始是写错了，原因是我又忽略了python中的引用传递，C++的后遗症。不能直接arg_list.pop()，要新设置一个list_new=arg_list[1:]\n",
    "# 每个递归函数里面会两次调用该递归函数，n次调用，因此为2**n，时间空间都是2**n。python列表复制是线性时间的话，准确来说是n*2**n。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归中很多子问题都会重复计算，因此可以用记忆搜索或者动态规划来解决。\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    for index,_ in enumerate(sorted(zip(arg_weight,arg_value))):\n",
    "        arg_weight[index]=_[0]\n",
    "        arg_value[index]=_[1]\n",
    "    m=arg_W+1\n",
    "    dp=[[0]*(m) for i in range(n)]\n",
    "    for i in range(m):\n",
    "        if i>=arg_weight[0]:\n",
    "            dp[0][i]=arg_value[0]\n",
    "    \n",
    "    index = 1\n",
    "    while index<=n-1:\n",
    "        dp[index][0]=0\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                dp[index][i]=dp[index-1][i]\n",
    "            # 能放进去\n",
    "            else:\n",
    "                dp[index][i]=max(dp[index-1][i],arg_value[index]+dp[index-1][i-arg_weight[index]])\n",
    "        index+=1\n",
    "    return dp[-1][-1]\n",
    "            \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[10,20,30]\n",
    "value=[60,100,120]\n",
    "W=50\n",
    "DP_solve(w,value,W)\n",
    "# 测试没问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[20,10,30]\n",
    "value=[100,60,120]\n",
    "W=50\n",
    "DP_solve(w,value,W)\n",
    "# 乱序之后测试也没问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 其实仔细一想，和顺序是没有关系的，因为每一步都会考虑是否可以放进去\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    # for index,_ in enumerate(sorted(zip(arg_weight,arg_value))):\n",
    "    #     arg_weight[index]=_[0]\n",
    "    #     arg_value[index]=_[1]\n",
    "    m=arg_W+1\n",
    "    dp=[[0]*(m) for i in range(n)]\n",
    "    for i in range(m):\n",
    "        if i>=arg_weight[0]:\n",
    "            dp[0][i]=arg_value[0]\n",
    "    \n",
    "    index = 1\n",
    "    while index<=n-1:\n",
    "        dp[index][0]=0\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                dp[index][i]=dp[index-1][i]\n",
    "            # 能放进去\n",
    "            else:\n",
    "                dp[index][i]=max(dp[index-1][i],arg_value[index]+dp[index-1][i-arg_weight[index]])\n",
    "        index+=1\n",
    "    return dp[-1][-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[20,10,30]\n",
    "value=[100,60,120]\n",
    "W=50\n",
    "DP_solve(w,value,W)\n",
    "# 确实，和顺序没什么关系"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 再做优化之前，先来证明“代码随想录”的逻辑错误\n",
    "# 我仔细看了下，这个人教程写错了，但是代码写对了，或许这就是程序员吧，anyway，还是很真诚地佩服尊重和感谢他"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "他的教程逻辑：\n",
    "\n",
    "![](./pics/%E6%95%99%E7%A8%8B%E9%80%BB%E8%BE%91.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我的反驳理由：\n",
    "\n",
    "![](./pics/%E5%8F%8D%E9%A9%B3%E7%90%86%E7%94%B1.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "他的代码逻辑：\n",
    "\n",
    "![](./pics/%E4%BB%A3%E7%A0%81%E9%80%BB%E8%BE%91.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 同理，这个DP是可以被优化的。\n",
    "# 优化空间到O(2*W)\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    cur=[0]*m\n",
    "    for i in range(m):\n",
    "        if i>=arg_weight[0]:\n",
    "            cur[i]=arg_value[0]\n",
    "    pre=cur[:]\n",
    "    index = 1\n",
    "    while index<=n-1:\n",
    "        cur[0]=0\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                cur[i]=pre[i]\n",
    "            # 能放进去\n",
    "            else:\n",
    "                cur[i]=max(pre[i],arg_value[index]+pre[i-arg_weight[index]])\n",
    "        pre=cur[:]\n",
    "        index+=1\n",
    "    return cur[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[20,10,30]\n",
    "value=[100,60,120]\n",
    "W=50\n",
    "DP_solve(w,value,W)\n",
    "# 测试通过，优化成功"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 同样的，可以优化到O(n)\n",
    "# def DP_solve(arg_weight,arg_value,arg_W):\n",
    "#     n=len(arg_weight)\n",
    "#     m=arg_W+1\n",
    "#     first_row=[0]*m\n",
    "#     for i in range(m):\n",
    "#         if i>=arg_weight[0]:\n",
    "#             first_row[i]=arg_value[0]\n",
    "#     cur=[0]*n\n",
    "#     pre=cur[:]\n",
    "#     index = 1\n",
    "#     while index<=m-1:\n",
    "#         cur[0]=first_row[index]\n",
    "#         for i in range(1,n):\n",
    "#             # 放不进去\n",
    "#             if index<arg_weight[i]:\n",
    "#                 cur[i]=pre[i-1]\n",
    "#             # 能放进去\n",
    "#             else:\n",
    "#                 cur[i]=max(pre[i-1],arg_value[i]+pre[i])  //写到这里发现无法实现，因为重量变化的跳度不是1，只用上一个pre实现不了，动态的不确定的，无法实现\n",
    "#         pre=cur[:]\n",
    "#         index+=1\n",
    "#     return dp[-1][-1]\n",
    "\n",
    "## 暂时认为不可以优化到O(n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一般来说DP是可以从2*n优化到n的，这里当然也可以从2*W优化到W。\n",
    "# 我之前为什么要用一个pre,因为cur[i]要用到cur[i-arg_wt[index]]，如果不用pre的话，cur[i-arg_wt[index]]已改变就不能算cur[i]了\n",
    "# 但是，我只会用到i前面的数据，所以如果我循环变量从后往前的话，前面的不就没变么，所以就可以用一个cur就ok了\n",
    "\n",
    "# 优化空间到O(W)\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    cur=[0]*m\n",
    "    for i in range(m):\n",
    "        if i>=arg_weight[0]:\n",
    "            cur[i]=arg_value[0]\n",
    "    # pre=cur[:]\n",
    "    index = 1\n",
    "    while index<=n-1:\n",
    "        # cur[0]=0\n",
    "        for i in range(m-1,0,-1):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                cur[i]=cur[i]\n",
    "            # 能放进去\n",
    "            else:\n",
    "                cur[i]=max(cur[i],arg_value[index]+cur[i-arg_weight[index]])\n",
    "        # pre=cur[:]\n",
    "        index+=1\n",
    "    return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w=[20,10,30]\n",
    "value=[100,60,120]\n",
    "W=50\n",
    "DP_solve(w,value,W)\n",
    "# 测试通过，优化成功。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 有一种常见优化递归的方法叫做记忆化搜索\n",
    "# 因为递归中会重复计算很多东西，如果我们能找到合适的数据结构，将我们已经算过的记录进去，那么就可以节省时空消耗"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归重复计算图解\n",
    "\n",
    "![](./pics/%E9%80%92%E5%BD%92%E9%87%8D%E5%A4%8D%E8%AE%A1%E7%AE%97.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 很显然，我们的DP数组就是可以用来存已经计算的结果的，其实，DP就是递归和记忆化搜索的产物。\n",
    "# 代码逻辑:计算过的就加到dp数组中，用到的结果，如果dp中已经存在，就直接从里面拿\n",
    "# 有点麻烦，算了懒得写了\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "# python 打包后排序的写法，zip()打包成zip对象，是一个iterable，然后可以调用sorted函数，可以指定key\n",
    "a=[3,1,4]\n",
    "b=[20,21,30]\n",
    "# a,b=[_ for _ in sorted(zip(a,b),key=lambda x: x[1])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 完全背包问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Unbounded Knapsack problem\n",
    "\n",
    "# 物品可以重复放入,不能只放入一部分，放入一部分的叫做fraction knapsack了。我应该不会深究了，学完完全背包就算了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "错误的贪心算法：我的最初想法，错误滴。\n",
    "\n",
    "![](./pics/%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E8%B4%AA%E5%BF%83.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "错误说明：\n",
    "\n",
    "![](./pics/%E8%B4%AA%E5%BF%83%E9%94%99%E8%AF%AF%E5%8E%9F%E5%9B%A0.PNG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 所以贪心在完全背包是行不通的\n",
    "# 我们直接来看动态规划的方法\n",
    "# 当然也可以用递归和记忆化搜索的方法来做\n",
    "# 但是既然它们都不如DP好，那就直接DP了\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二维DP：参照下图，之后的一维DP就是在这个基础上优化空间的\n",
    "\n",
    "![](./pics/%E4%BA%8C%E7%BB%B4DP.PNG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 话不多说，上代码\n",
    "\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    dp=[[0]*m for i in range(n)]\n",
    "    # 先填充第一行\n",
    "    for i in range(1,m):\n",
    "        dp[0][i]=(i//arg_weight[0])*arg_value[0]\n",
    "    # 先loop物品，再loop容量\n",
    "    index=1\n",
    "    while index<=n-1:\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                dp[index][i]=dp[index-1][i]     # 放不进去就容量不变，但是物品只能放索引到index-1的\n",
    "            # 能放进去\n",
    "            else:\n",
    "                dp[index][i]=max(dp[index-1][i],arg_value[index]+dp[index][i-arg_weight[index]])    #放进去了，加上value，容量改变，但是还是可以放到索引为index，至于之后能不能，反正进入循环就再判断呗\n",
    "        index+=1\n",
    "    return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "300\n"
     ]
    }
   ],
   "source": [
    "wt1=[2,3,1]\n",
    "val1=[10,12,3]\n",
    "W1=4\n",
    "print(DP_solve(wt1,val1,W1))\n",
    "wt2=[5, 10, 15]\n",
    "val2=[10, 30, 20]\n",
    "W2=100\n",
    "print(DP_solve(wt2,val2,W2))\n",
    "# 测试通过\n",
    "# 而且和顺序无关，填一下DP表就清楚了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 继续用二维DP，先loop容量，再loop物品\n",
    "\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    dp=[[0]*m for i in range(n)]\n",
    "    # 第一列初始化的时候已经填充好，全部为0\n",
    "    # 先loop容量，再loop物品\n",
    "    col_index=1\n",
    "    while col_index<=m-1:\n",
    "        for i in range(0,n):\n",
    "            # 装不进去\n",
    "            if arg_weight[i]>col_index:\n",
    "                dp[i][col_index]=dp[i-1][col_index]     # 装不进去就不装，容量不变，物品还是只能装前面的，前面的能不能装进去不用管，反正在循环判断过了\n",
    "            # 能装进去\n",
    "            else:\n",
    "                dp[i][col_index]=max(dp[i-1][col_index],arg_value[i]+dp[i][col_index-arg_weight[i]])    #装进去了，加上value，容量改变，但是还是可以放到索引为i的，至于之后能不能，反正进入循环就再判断呗\n",
    "        col_index+=1\n",
    "    return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "300\n"
     ]
    }
   ],
   "source": [
    "wt1=[2,3,1]\n",
    "val1=[10,12,3]\n",
    "W1=4\n",
    "print(DP_solve(wt1,val1,W1))\n",
    "wt2=[5, 10, 15]\n",
    "val2=[10, 30, 20]\n",
    "W2=100\n",
    "print(DP_solve(wt2,val2,W2))\n",
    "# 测试通过"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 优化空间写法,优化到O(2*W)\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    cur=[0]*m\n",
    "    # 先填充第一行\n",
    "    for i in range(1,m):\n",
    "        cur[i]=(i//arg_weight[0])*arg_value[0]\n",
    "    pre=cur[:]\n",
    "    # 先loop物品，再loop容量\n",
    "    index=1\n",
    "    while index<=n-1:\n",
    "        cur[0]=0\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                cur[i]=pre[i]     # 放不进去就容量不变，但是物品只能放索引到index-1的\n",
    "            # 能放进去\n",
    "            else:\n",
    "                cur[i]=max(pre[i],arg_value[index]+cur[i-arg_weight[index]])    #放进去了，加上value，容量改变，但是还是可以放到索引为index，至于之后能不能，反正进入循环就再判断呗\n",
    "        pre=cur[:]\n",
    "        index+=1\n",
    "    return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "300\n"
     ]
    }
   ],
   "source": [
    "wt1=[2,3,1]\n",
    "val1=[10,12,3]\n",
    "W1=4\n",
    "print(DP_solve(wt1,val1,W1))\n",
    "wt2=[5, 10, 15]\n",
    "val2=[10, 30, 20]\n",
    "W2=100\n",
    "print(DP_solve(wt2,val2,W2))\n",
    "# 测试通过"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 优化空间到O(W)\n",
    "def DP_solve(arg_weight,arg_value,arg_W):\n",
    "    n=len(arg_weight)\n",
    "    m=arg_W+1\n",
    "    cur=[0]*m\n",
    "    # 先填充第一行\n",
    "    for i in range(1,m):\n",
    "        cur[i]=(i//arg_weight[0])*arg_value[0]\n",
    "    # pre=cur[:]\n",
    "    # 先loop物品，再loop容量\n",
    "    index=1\n",
    "    while index<=n-1:\n",
    "        cur[0]=0\n",
    "        for i in range(1,m):\n",
    "            # 放不进去\n",
    "            if arg_weight[index]>i:\n",
    "                cur[i]=cur[i]     # 放不进去就容量不变，但是物品只能放索引到index-1的\n",
    "            # 能放进去\n",
    "            else:\n",
    "                cur[i]=max(cur[i],arg_value[index]+cur[i-arg_weight[index]])    #放进去了，加上value，容量改变，但是还是可以放到索引为index，至于之后能不能，反正进入循环就再判断呗\n",
    "        # pre=cur[:]\n",
    "        index+=1\n",
    "    return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "300\n"
     ]
    }
   ],
   "source": [
    "wt1=[2,3,1]\n",
    "val1=[10,12,3]\n",
    "W1=4\n",
    "print(DP_solve(wt1,val1,W1))\n",
    "wt2=[5, 10, 15]\n",
    "val2=[10, 30, 20]\n",
    "W2=100\n",
    "print(DP_solve(wt2,val2,W2))\n",
    "# 测试通过\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 01背包具体习题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 416. 分割等和子集\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 完全背包具体问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 其他动态规划习题合辑"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 53. 最大子数组和\n",
    "# 198. 打家劫舍\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NP问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 回溯算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 回溯法是一种很自然的想法，到了该回溯的地方（循环触底）就回溯，关键在于如何设计代码来实现这个回溯的效果\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python内存机制（与C++、Java对比）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[100]\n",
      "[100, '000']\n",
      "[100, '000']\n"
     ]
    }
   ],
   "source": [
    "# 最好不要将值传递和引用传递这种概念带到python中来，我们可以理解成Python中所有参数传递都是引用传递，传递的都是地址。\n",
    "# 我看过一些文章说引用传递的本质还是值传递，首先不知道他说对了没有，其次就算他说对了，也是python的底层机制，但是在顶层使用上来看，传递的都是地址。\n",
    "# 这里目前不是在讨论引用传递的问题，但是你需要知道python永远都是引用传递\n",
    "# 观察这段代码,foo没有改变a的值，foo2改变了a的值\n",
    "def foo(arg_list):\n",
    "    arg_list=[1,2,3]\n",
    "    return arg_list\n",
    "def foo2(arg_list):\n",
    "    arg_list.append(\"000\")\n",
    "    return arg_list\n",
    "a=[100]\n",
    "print(foo(a))\n",
    "print(a)\n",
    "a=[100]\n",
    "print(foo2(a))\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a的id: 1935961385328\n",
      "b的id和a的id一样: 1935961385328\n",
      "b的新id为: 1935961385360\n",
      "a的id是: 1935961385392\n"
     ]
    }
   ],
   "source": [
    "# 为了解决上面这个问题，先来了解python的内存机制\n",
    "# 这四行代码道出了python内存机制的精髓，观察id(a),id(b)\n",
    "a=3     #a指向3\n",
    "print(f'a的id: {id(a)}')\n",
    "b=a     #“=”右边是变量，则不会生成新id,b也指向3\n",
    "print(f'b的id和a的id一样: {id(b)}')\n",
    "b=4     #当多个变量同是指向某对象时，新赋值(\"=\"右边是常量)会生成新id\n",
    "print(f'b的新id为: {id(b)}')\n",
    "a=5     #改变内存上的值，改变id\n",
    "print(f'a的id是: {id(a)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./pics/a%3D3.png)\n",
    "\n",
    "![](./pics/ab%3D3.png)\n",
    "\n",
    "![](./pics/b%3D4.png)\n",
    "\n",
    "![](./pics/a%3D5.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a的id: 1936054881856\n",
      "在“=”赋值前arg_list的id和a一样都是: 1936054881856\n",
      "在“=”赋值后arg_list的id: 1936054724288\n",
      "[1, 2, 3]\n",
      "[100]\n",
      "a的id: 1936054724288\n",
      "append前的arg_list的id一样: 1936054724288\n",
      "append后的arg_list的id还是一样: 1936054724288\n",
      "[10, '000']\n",
      "[10, '000']\n"
     ]
    }
   ],
   "source": [
    "# 原因在这里：在python中每一次用“=”重新(该变量已存在)赋值（常数值）a=100。不包括新建对象，比如a=ListNode(100)都会重新生成新id，新内存地址。\n",
    "# 如果等号赋值（变量值）root_=root，则不会生成新id，root指向谁，root_就指向谁。\n",
    "def foo(arg_list):\n",
    "    print(f'在“=”赋值前arg_list的id和a一样都是: {id(arg_list)}')\n",
    "    arg_list=[1,2,3]\n",
    "    print(f'在“=”赋值后arg_list的id: {id(arg_list)}')\n",
    "    return arg_list\n",
    "def foo2(arg_list):\n",
    "    print(f'append前的arg_list的id一样: {id(arg_list)}')\n",
    "    arg_list.append(\"000\")\n",
    "    print(f'append后的arg_list的id还是一样: {id(arg_list)}')\n",
    "    return arg_list\n",
    "a=[100]\n",
    "print(f'a的id: {id(a)}')\n",
    "print(foo(a))\n",
    "print(a)\n",
    "a=[10]\n",
    "print(f'a的id: {id(a)}')\n",
    "print(foo2(a))\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# 有人会有疑问，说我上面写的是可变对象做参数，传递的才是地址，如果参数是不可变的，传递的是值。这是我们上课老师说的，但我认为他搞错了。\n",
    "# 按照老师这种理解，操作起来好像也没问题，但是确实是错误的，每次还要分析是不是可变对象，破坏了python的统一性。\n",
    "# 老师产生这种错误认知的原因是用C++太多了，因为C++是默认值传递的\n",
    "# 但是C++赋值号也只是浅拷贝，只会拷贝复杂结构的第一层。（我在  “剑指 Offer 22. 链表中倒数第k个节点”  做过测试）。\n",
    "# C++传参也是浅拷贝，因而看起来：不可变对象值传递，可变对象引用传递。其实就是值传递，只不过是浅拷贝罢了。\n",
    "# 观察这段经典的swap交换代码，观察id(a),id(b),id(arg1),id(arg2)\n",
    "# 由此得出结论：至少从使用的角度来看，可以认为python参数传递永远传递的是地址\n",
    "# java传递的也是地址，也是引用传递，而且赋值号也是同python直接指向一个地址，连浅拷贝都没有。（在“160. 相交链表”中做过测试）。\n",
    "def swap(arg1,arg2):\n",
    "    print(id(a)==id(arg1))\n",
    "    print(id(b)==id(arg2))  #证明传递的是地址\n",
    "    arg1,arg2=arg2,arg1\n",
    "    print(id(a)==id(arg2))\n",
    "    print(id(b)==id(arg1))  #证明交换的是地址\n",
    "a,b=6,9\n",
    "swap(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 9\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# 上面arg1,arg2=arg2,arg1完全等价与下面，从下面的代码更加可以解释为什么交换的是地址\n",
    "def swap2(arg1,arg2):\n",
    "    tmp=arg1\n",
    "    arg1=arg2\n",
    "    arg2=tmp\n",
    "a,b=6,9\n",
    "swap2(a,b)\n",
    "print(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 6\n"
     ]
    }
   ],
   "source": [
    "# 可以用return交换\n",
    "# 如果是C++可以直接拿内存上的值&a,&b\n",
    "def swap3(arg1,arg2):\n",
    "    arg1,arg2=arg2,arg1\n",
    "    return arg1,arg2\n",
    "a,b=6,9\n",
    "a,b=swap3(a,b)\n",
    "print(a,b)\n",
    "\n",
    "# 弄清楚这些问题只是为了提高自己的debug效率\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 其他细节"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 函数默认参数\n",
    "![](./pics/%E9%BB%98%E8%AE%A4%E5%8F%82%E6%95%B0.png)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['wuhu', 100]\n",
      "[100]\n",
      "[100, 100]\n"
     ]
    }
   ],
   "source": [
    "# 函数的默认值不是每次调用都会创建的，默认值只会在函数定义的时候创建一次\n",
    "def add(num=[]):\n",
    "    num.append(100)\n",
    "    return num\n",
    "a=['wuhu']\n",
    "print(add(a))\n",
    "print(add())\n",
    "print(add())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[100]\n",
      "[100]\n",
      "[100]\n"
     ]
    }
   ],
   "source": [
    "def add2(num=[]):\n",
    "    num=[100]\n",
    "    return num\n",
    "a=[\"wuhu\"]\n",
    "print(add2(a))\n",
    "print(add2())\n",
    "print(add2())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 推荐写法：\n",
    "def add(num=None):\n",
    "    if num==None:\n",
    "        num=[]\n",
    "        # do your things\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "fcde990f9140614acfcf011c3251f5c500b1a43ee1bc68457481590075bcff1b"
  },
  "kernelspec": {
   "display_name": "Python 3.9.5 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
